\section{Preliminary computational experiments}

In this section we provide preliminary computational experiments with the
stability number of $G$ in order
to explore whether the proposed method is useful as a cut generating tool or
not. Our main goal is not to provide a competitive algorithm for the maximum
stable set problem, since combinatorial algorithms are much more effective than
cutting-plane algorithms for this problem. Instead, we intend to assess whether the proposed procedure is
effective at generating generalized rank cuts for the stable set polytope.
To this end, we implemented the cut-generating procedure as a separation
procedure attached to \textsc{Cplex} 12.6's branch and cut algorithm to compute
a strengthened upper bound for the root subproblem. Whenever a fractional
solution is found, we execute the cut-generating procedure several times, each
execution starting from a different clique in the role of $W_1$. For each
initial clique, we generate a sequence of clique projections until a simple
greedy heuristic finds a violated clique inequality. When this happens, we apply
the clique-lifting procedure of Lemma~\ref{lem:stlifting} and add the generated
inequality if it is violated by the fractional solution at hand.

Table~\ref{tab:resultsDIMACS} summarizes the preliminary experiments with some
instances from the DIMACS benchmark and for random graphs.
The notation $G(n,d)$ specifies random graphs with $n$ vertices and a density of
$d\in[0,1]$, and for these instances we report the average results over five
randomly-generated instances. The experiments were performed on a 32-bit
personal computer, with a time limit of five minutes. The preprocessing, cut
generation, and variable fixing procedures from \textsc{Cplex} are turned off.
Following the approach used in \cite{Rossi.Smriglio.01}, for each graph we
choose the best parameters and report the obtained results. The first four
columns contain the instance name, the number of vertices, the graph density,
and its stability number. The following three columns contain data for the root
note in the enumeration tree: the column ``UB'' contains the upper bound after the
last successful execution of the cut-generating procedure, and the column ``Time'' reports the total time spent at the root node, in seconds. 
The columns UB\cite{Rossi.Smriglio.01} and UB\cite{Pardalos} contain the best upper bound attained in \cite{Rossi.Smriglio.01} and \cite{Pardalos}, respectively. Finally, the last three columns contain the number of generated clique cuts, violated rank inequalities, and violated generalized rank inequalities, respectively.
As Table~\ref{tab:resultsDIMACS} shows, and similarly to the results
in~\cite{Correa14}, the procedure is able to generate a large number of cuts,
and provides upper bounds that are competitive with those generated in \cite{Pardalos} and \cite{Rossi.Smriglio.01} for a representative sample of benchmark graphs.
As a future work, we intend to perform
extensive computational experiments with the proposed cut generating procedure
applied for other optimization problems involving stable sets, like, for
instance, the vertex coloring problem.

\begin{table*}[htbp]
\caption{Results for graphs selected from the DIMACS benchmark and
randomly generated.}
\label{tab:resultsDIMACS}
\centering
{\scriptsize
\begin{tabular}{cccccccccc} \hline
%Encabezado fila 1
\multicolumn{3}{l}{Instances} & \multicolumn{3}{l}{UB per type of cuts} &
\multicolumn{1}{l}{Time (sec.)} & \multicolumn{2}{l}{Number of cuts} \\
\cline{1-3} \hline
%Encabezado fila 2
$G=(V,E)$ & $|V|$/Dens. & $\alpha(G)$ & Rank/W & Clique & \cite{Pardalos} &&
Rank/W & Clique \\ \hline
\hline
%Datos
\input{resultados2.0-dimacs.tex}
\hline \hline
\input{resultados2.0-rand.tex}
 \hline
\end{tabular}}
\end{table*}
